package com.fps.webshop.question.question0700_0799;

import com.fps.webshop.question.common.TreeNode;

/**
 * 700. 二叉搜索树中的搜索
 * 
 * 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
 * 
 * 例如，
 * 
 * 给定二叉搜索树:
 *         4
 *        / \
 *       2   7
 *      / \
 *     1   3
 * 和值: 2
 * 
 * 你应该返回如下子树:
 *       2     
 *      / \   
 *     1   3
 * 在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
 */
public class Question700 {
	
	/**
	 * 第一次提交，二叉树递归调用
	 * 二叉树通用解法，没注意是二叉搜索树（左子树节点小于根节点，右子树节点大于根节点）
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	39.2 MB	Java	2021/08/24 10:39
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：39.2 MB, 在所有 Java 提交中击败了62.94%的用户
	 */
	public static TreeNode searchBST1(TreeNode root, int val) {
		if(root==null) {
			return null;
		}
		if(root.val==val) {
			return root;
		}else {
			TreeNode s = searchBST1(root.left,val);
			return s==null?searchBST1(root.right,val):s;
		}
    }
	
	/**
	 * 第2次提交，二叉树递归调用，利用是二叉搜索树的特性
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	39.3 MB	Java	2021/08/24 10:46
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：39.3 MB, 在所有 Java 提交中击败了44.95%的用户
	 */
	public static TreeNode searchBST2(TreeNode root, int val) {
		if(root==null||root.val==val) {
			return root;
		}else {
			return root.val>val?searchBST2(root.left,val):searchBST2(root.right,val);
		}
    }
    
	/**
	 * 第3次提交，官方迭代
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	39.4 MB	Java	2021/08/24 10:49	
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：39.4 MB, 在所有 Java 提交中击败了36.78%的用户
	 */
	public TreeNode searchBST(TreeNode root, int val) {
		while (root != null && val != root.val)
			root = val < root.val ? root.left : root.right;
		return root;
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		TreeNode leftNode1 = new TreeNode(2);
		//TreeNode rightNode1 = new TreeNode(-57);
		root.left = leftNode1;
		//root.right = rightNode1;
		
		//TreeNode rightNode2 = new TreeNode(67);
		//leftNode1.right = rightNode2;
		
		//TreeNode leftNode3 = new TreeNode(67);
		//rightNode1.left = leftNode3;
		
		System.out.print(searchBST1(root,1));
		
	}
}
